package demo02;

import java.util.Random;
//数组前k个最小值(快速选择算法)
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int l = 0,r = nums.length-1;
        return find(nums,l,r,k);
    }
    public int find(int[] nums,int l,int r,int k){
        //找随机值
        int n = new Random().nextInt(r-l+1)+l;
        int key = nums[n];
        int left = l - 1,right = r + 1,i = l;
        while(i<right){
            if(nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        if((r-right+1) >= k) return find(nums,right,r,k);
        else if((r-left)>=k) return key;
        else return find(nums,l,left,k-(r-left));
    }
    public void swap(int[] nums,int left,int right){
        int t = nums[left];
        nums[left] = nums[right];
        nums[right] = t;
    }
}